Many business, engineering, and scientific operations involve multiple steps and are implemented on a number of processors such as computers, each of which uses data maintained in one or more databases. The processors are connected to enable communication. For example, in a business operation, a design (e.g., software designs for controlling finance or machines) might include preparing the specification and implementation according to the specification. Such a business operation can involve many computers and transactions. Requests are sent by one computer to others. The requests are acted upon, then the database in each computer involved is updated. One approach to handle such transactions is to link them each as atomic action, some of which links may be sequential, concurrent, or both. This is the "flat transaction" structure. See, e.g., Leymann et al., "Business process management with flowmark," Proc. Compcon '94, 1994; and McCarthy et al., "Workflow and transactions in concert," Bulletin of the Technical Committee on Data Engineering, IEEE Computer Society, 16(2),1993.
Occasionally, in transactions, a fault may occur. Examples of faults are communication line failure, equipment inoperability or unavailability, and the like. Investigations on techniques in managing computer systems to overcome faults and their effect in transactions have been reported. One approach involves nested transactions, in which parallel subtransactions can be executed (see., e.g., Dayal, et al. "A Transactional Model for Long-Running Activities," Proceedings of the 17th International Conf Very Large Data Bases, pp. 113-122, Barcelona, Sept., 1991). A process involving a database in a computing node can be modeled as layers of transactions. Such a layering structure introduced intermediate level of control, allowing failure recovery at certain levels.
In general, relating to fault-tolerant computer systems, a transaction is a performance of a number of actions on data in a database. Generally, a transaction can have a number of subtransactions. Furthermore, each subtransaction can itself have a number of subtransactions. Transactions, including those transactions that are themselves subtransactions, that have subtransactions are considered to be "parents." Subtransactions of parents are the "children" of the parents. Parents and children can be arranged in a hierarchy of blocks. A block can itself be a hierarchy containing a hyperactivity that has subactivities. That is, a transaction, T, may have subtransactions and be itself considered a block, denoted by B.sup.T, of subtransactions. The transaction T is referred to as the hyper-transaction.
A transaction, which may be a subtransaction of another transaction, is committed when the effects of its execution are made permanent and become visible to other transactions, depending on its scope of commitment. If a transaction cannot be completed, as when there is a fault, it is aborted. A transaction is terminated when it has been committed or aborted. Otherwise, it is considered to be in progress. A transaction is performed with atomicity if in its performance all or none of the actions in the transaction are completed. In some cases, transactions have more relaxed atomicity in the sense that the transaction is committed only if all of its critical actions are completed or compensated. If a child transaction cannot commit or be compensated for, then the effect of the transaction is not completed and any tentatively committed subtransaction is undone, thereby aborting the whole transaction. A subtransaction is compensatable if the execution of another subtransaction at the first subtransaction's local site can compensate for the effects of its execution. A compensating transaction undoes any effect of a transaction for which it compensates, but does not necessarily restore the database in which the compensated-for transaction is executed to its original state prior to the execution.
Sometimes multiple concurrent, in-progress transaction hierarchies (i.e., involving different databases) may need to be coordinated to accomplish a process. In other words, a process may depend on a transaction of another process, i.e., there are dependencies crosstransaction hierarchies. For example, in the software design case above, if for some reason a transaction in preparing the specification fails, it may cause the failure of a transaction in the process of implementing the specification (once it has commenced). The failure in the implementation process would have to be recovered. In the transaction hierarchy representing a transaction process, a failure of a subtransaction may cause its parent to fail, and the failure may propagate to higher level ancestors as well. Mechanisms have been proposed for determining the failure scope and for logically rolling back the business process in that scope. See, e.g., Weikum et al., "Concepts and applications of multilevel transactions and open nested transaction," Transaction Models for Advanced Database Applications, A. Elmagamid (ed.), Morgan-Kaufmann, 1992.
Up to now, mechanisms have been reported only for application to a single transaction hierarchy and they do not readily support failure handling across transaction hierarchies. Handling failures across transaction hierarchies differs significantly from doing the same in a single transaction hierarchy. In a single transaction hierarchy, a parent transaction may not terminate until all its child transactions terminate. Thus, when a failure occurs, the parent and the direct ancestors of the originally failed transaction are still in progress, making it feasible to pass control up the hierarchy. In contrast, when a transaction failure is caused by the failure of another transaction from another transaction hierarchy, a transaction, which should abort as a result of the failure, may have been committed already. In this situation, committed transactions at certain levels should be invalidated by compensation. In a flat transaction scheme, the transaction can only commit to the public database. Failure handling is accomplished by undoing the transaction starting from the failed item in the sequence before the transaction is committed. The effect of the failure is not known to the outside. Only failures in the sequence of the transaction can be handled. For this reason, existing failure handling techniques are not adequate for recovering from cross-hierarchy failures. Thus the flat transaction scheme lacks the capacity to handle cross-steps or cross-hierarchy transaction failures or exceptions. What is needed is a technique for efficiently handling such cross-hierarchy transaction failures.